1. Field of the Invention
The present invention relates to register allocation for instruction level parallel architectures.
2. Related Art
Generally, a program written in a programming language is optimized in many ways. As one optimization method, register allocation is conducted to obtain an effective usage of registers. According to one method for allocating registers, called coloring, a different color is assigned to each of the registers, and subsequently, registers are allocated based on the same principle as would be used for a process whereby colors were used to distinguish between program instructions.
Accompanying the improvements in the hardware functions of computers, parallel processing, involving multi-programming, has become popular. Also, for the allocation of registers for compiling, a register allocation method has been proposed that reflects the parallel execution of a program. For this type of register allocation for instruction level parallel architectures, it is important to suppress the deterioration of the parallel execution of instructions due to the generation of anti dependencies.
One conventional register allocation method, proposed by S. S. Pinter, is a coloring method that uses a parallelizable interference graph. This method is described in detail in reference document, “Register Allocation With Instruction Scheduling: A New Approach”, S. S. Pinter, SIGPLAN '93 Conference On PLDI.
According to the graph coloring method using a parallelizable interference graph, it is assumed that an interference will occur between variables that are used for instructions executed in parallel, and different registers are allocated for variables that interfere with each other. With this method, anti dependencies between instructions that are to be executed in parallel are removed, and the parallel execution of code is ensured.